package com.lun.swordtowardoffer2.c10;

public class Trie {

	static class TrieNode{
		static final int ENGLISH_LOWER_LETTER_TOTAL_NUM = 'z' - 'a' + 1;
		TrieNode children[];
		boolean isWord;
		
		public TrieNode() {
			children = new TrieNode[ENGLISH_LOWER_LETTER_TOTAL_NUM];//元素并未实例化
		}
	}
	
	private TrieNode root;
	
	public Trie() {
		root = new TrieNode();
	}
	
	public void insert(String word) {
		TrieNode node = root;
		for(char ch : word.toCharArray()) {
			if(node.children[ch - 'a'] == null) {
				node.children[ch - 'a'] = new TrieNode();
			}
			node = node.children[ch - 'a'];
		}
		node.isWord = true;
	}
	
	public boolean search(String word) {
		TrieNode node = searchCore(word);
		return node != null && node.isWord;
	}
	
	public boolean startsWith(String prefix) {
		return searchCore(prefix) != null;
	}
	
	private TrieNode searchCore(String str) {
		TrieNode node = root;
		for(char ch : str.toCharArray()) {
			if(node.children[ch - 'a'] == null) {
				return null;
			}
			node = node.children[ch - 'a'];
		}
		return node;
	}
}
